package com.company.动态规划;

public class Leet1143 {
    //从后往前更好，就不用变量s1,s2了
    private String s1,s2;
    private int dfs(int i, int j){
        if(i==s1.length()||j==s2.length())
            return 0;

        //其实这样剪枝很不好，应该遍及所有二维状态(i,j)，再剪枝
        int k=j;
        while(k<s2.length()&&s2.charAt(k)!=s1.charAt(i))
            k++;
        if(k==s2.length())
            return dfs(i+1,j);

        return Math.max(dfs(i+1,j),dfs(i+1,k+1)+1);
    }
    public int longestCommonSubsequence(String text1, String text2) {
        this.s1 = text1;
        this.s2 = text2;
        return dfs(0,0);
    }
}
